package com.epam.rd.mycollections;

import java.util.Comparator;
import java.util.Iterator;
import java.util.RandomAccess;

public class MyCollections {

    public static <E extends Comparable<? super E>> void sort(MyList<E> list) {
        if (list instanceof RandomAccess) {
            quickSort(list, null, 0, list.size() - 1);
        } else {
            bubbleSort(list, null);
        }
    }

    public static <E> void sort(MyList<E> list, Comparator<? super E> comp) {
        if (list instanceof RandomAccess) {
            quickSort(list, comp, 0, list.size() - 1);
        } else {
            bubbleSort(list, comp);
        }
    }

    private static <E> int
            compare(E left, E right, Comparator<? super E> comp) {
        int result;
        if (comp == null) {
            result = ((Comparable<? super E>) left).compareTo(right);
        } else {
            result = comp.compare(left, right);
        }
        return result;
    }

    private static <E> void bubbleSort(MyList<E> list,
            Comparator<? super E> comp) {
        for (int i = 0; i < list.size(); i++) {
            for (int j = i; j < list.size(); j++) {
                if (compare(list.get(i), list.get(j), comp) > 0) {
                    swap(list, i, j);
                }
            }
        }
    }

    private static <E> void quickSort(MyList<E> list,
            Comparator<? super E> comp, int first, int last) {
        if (first >= last) {
            return;
        }
        int i = first;
        int j = last;
        E elem = list.get((i + j) >> 1);
        while (i <= j) {
            while (compare(list.get(i), elem, comp) < 0) {
                i++;
            }
            while (compare(list.get(j), elem, comp) > 0) {
                j--;
            }
            if (i <= j) {
                swap(list, i, j);
                i++;
                j--;
            }
        }
        quickSort(list, comp, first, j);
        quickSort(list, comp, i, last);
    }

    public static <E> void swap(MyList<E> list, int i, int j) {
        E elementI = list.get(i);
        E elementJ = list.get(j);
        list.set(i, elementJ);
        list.set(j, elementI);
    }

    public static <E> void copy(MyList<? super E> dest,
            MyList<? extends E> src) {
        if (dest.size() < src.size()) {
            throw new MyIndexOutOfBoundsException();
        }
        Iterator<? extends E> iterator = src.iterator();
        int index = 0;
        while (iterator.hasNext()) {
            dest.set(index++, iterator.next());
        }
    }

    public static <E> void reverse(MyList<E> list) {
        for (int i = 0; i < list.size() >> 1; i++) {
            swap(list, i, list.size() - i - 1);
        }
    }

    public static <E extends Comparable<? super E>> int binarySearch(
            RandomAccess list, E key) {
        MyArrayList<? extends Comparable<? super E>> arrayList =
                (MyArrayList<? extends Comparable<? super E>>) list;
        int left = 0;
        int right = arrayList.size() - 1;
        int mid = (left + right) >> 1;
        int result;
        if (arrayList.get(left).compareTo(key) > 0) {
            result = -1;
        } else if (arrayList.get(right).compareTo(key) < 0) {
            result = -1 - arrayList.size();
        } else {
            while (left <= right) {
                mid = (left + right) >> 1;
                if (arrayList.get(mid).compareTo(key) > 0) {
                    right = mid - 1;
                } else if (arrayList.get(mid).compareTo(key) < 0) {
                    left = mid + 1;
                } else {
                    break;
                }
            }
            if (arrayList.get(mid).compareTo(key) != 0) {
                result = -1 - mid;
            } else {
                result = mid;
            }
        }
        return result;
    }
}
